S3 Group

The S3 group is the group of permutation on 3 elements. It has 6 elements. It is the group of all the automorphism on the set {1, 2, 3}.

Here is the full list of the elements of S3:

## e: ()
## a: (1,2)
## b: (1,3)
## c: (2,3)
## p: (1,2,3)
## p^2: (1,3,2)

Table of S3:

S3 e p p2 a b c
e e p p2 a b c
p p p2 e c a b
p2 p2 e p b c a
a a b c e p p2
b b c a p2 e p
c c a b p p2 e

Order of the elements:

S3 Order Sign Inversions
e 1 + 0
p 3 + 0
p2 3 + 0
a 2 - 1
b 2 - 1
c 2 - 1

Unique normal chain decomposition of S3:

\[ C(2) \lhd C(3) \lhd S_3\]

And this decomposition is unique, the factors cannot be swapped.

Cycle graph

grViz('
graph cycle {
 graph[layout = neato]
 node [shape = circle, style = filled, color = grey, label=""]

 e [color = red]; a; b; c; p; p2

  e -- a
  e -- b
  e -- c
  e -- p -- p2 -- e
}
')

Subgroups of S3

###

is a normal subgroup

The group <p> = {e, p, p2} is normal in S3:

all(p^a == p2, p^b == p2, p^c == p2)
## [1] TRUE

The classes of <p> in S3 are:

{e, p, p2}, {a, b, c}

The action of a on <p>: (p p2)

More detailed action of the group on <p>:

S3 {e, p, p2} {a, b, c}
e {e, p, p2} {a, b, c}
a {a, b, c} {e, p, p2}
b {b, c, a} {p2, e, p}
c {c, a, b} {p, p2, e}
p {p, p2, e} {c, a, b}
p2 {p2, e, p} {b, c, a}

<p> is isomorphic to Z/3Z and it has no non-trivial subgroups.

If G is a subgroup of S3 containing <p> then G*<p> is a subgroup of S3/<p>. S3/<p> is a group of order 2 so it is isomorphic to Z/2Z and it has no non trivial subgroup. The only subgroups containing p are {e} and S3.

If G is a sub-group not including <p>. Then inter(G, <p>) is {e}. because inter(G, <p>) is a subgroup of <p> and it cannot be <p> because G does no include <p>.

So G is included in {e, a, b, c}. G cannot contain more than 2 elements because any of products ab, bc, … will yield an element of <p>. So G is either {e, a}, {e, b}, {e, c}.

Conclusion: Here is the full list of the subgroups of S3: {e}, {e, a}, {e, b}, {e, c}, {e, p, p2}, {e, a, b, c, p, p2}

Lattice of all the subgroups

## Warning in .Call("R_igraph_layout_fruchterman_reingold", graph, coords, :
## '.Random.seed' is not an integer vector but of type 'NULL', so ignored

Normal subgroups

Actions of the group

The natural action of S3 on {1, 2, 3}

This is a faithful action.

We can compute the orbits:

S3 Orbits
e {1} {2} {3}
a {1, 2} {3}
b {1, 3} {2}
c {1} {2, 3}
p {1, 2, 3}
p2 {1, 2, 3}

We can also compute the stabilizers:

{1, 2, 3} Stabilizer
1 <c>
2 <b>
3 <a>

Action on the ‘edges’

We consider the action of S3 on this set: {{1, 2}, {1, 3}, {2, 3}}

  • Action of <p>
## [1] TRUE
  • Action of a:
all(
  a_f(c(1, 2)) == c(2, 1),
  a_f(c(1,3)) == c(2, 3),
  a_f(c(2, 3)) == c(1, 3))
## [1] TRUE

Since a and p generate S3 we deduce that the action is faithfull.

Orbits

S3 Orbits
e {1_2} {1_3} {2_3}
a {1_2} {1_3, 2_3}
b {1_2, 2_3} {1_3}
c {1_2, 1_3} {2, 3}
p {1_2, 2_3, 1_3}
p2 {1_2, 2_3, 1_3}

Stabilizers

Action on the elements of order 2

The elements of order 2 are: a, b, c

c(a^p == c, a^(p^2) == b)
## [1] TRUE TRUE

So the action is transitive. And |O(a)|.|Stab(a)| = 6 => 3.|Stab| = 6 So the stabilizer size is 2.

And:

S3 Stab
a e, a
b e, b
c e, c

Action on the elements of order 3

The elements of order 3 are: p, p^2

c(p^a == p^2)
## [1] TRUE

So the action is transitive and: |O(p)|.|Stab(p)| = 6 so |Stab(p)| = 2

S3 Stab
p e, p, p2
p2 e, p, p2

Beat actions

S3 has an action on

Beat 1 2 3 4 5 6
1 x x x x x x
2 x x x x x x
p.1 1 2 3 4 5 6
p.2 3 1 2 6 4 5
a.1 4 5 6 1 2 3
a.2 1 2 3 4 6 5
p2.2 2 3 1 5 6 4
apa.2 3 1 2 5 6 4

The action of p on the first layer is the trivial one. The action of a on the first layer just switches 2 the 2 3-blocks.

The action of p on the second layer circulates the 2 3-blocks. It has 2 orbits. The action of a on the second layer first 3-block is the trivial one. On the second 3-block it switches 5 and 6.

In order to define the action we remember this following presentation of S3: \(<a^2, p^3, apa = p^2>\)

Check that the action on the first row is an action: \(\phi_1(a) = (1 4) (2 5) (3 6)\) \(\phi_1(p) = id\)

The images verify all the relations, so it is indeed an action.

Check that the action on the second row is an action: \(\phi_2(a) = (5 6)\) \(\phi_2(p) = (1 2 3) (4 5 6)\)

gp <- as.cycle(1:3) * as.cycle(4:6)
ga <- as.cycle(5:6)

So apparently this is not an action since gp^ga != gp^2

gp^ga == gp^2
## [1] FALSE

We can try this one:

Beat 1 2 3 4 5 6
a.2 4 5 6 1 3 2

We have for the second row:

ga <- as.word(c(4, 5, 6, 1, 3, 2))

This also doesn’t work since ga^2 is not identity.

What about this one?

Beat 1 2 3 4 5 6
p.2 2 3 1 5 6 4
a.2 4 6 5 1 3 2
ga <- as.word(c(4, 6, 5, 1, 3, 2))
cat('ga: ', as.character(as.cycle(ga)), '\r\n')
## ga:  (1,4)(2,6)(3,5) 
cat('gp: ', as.character(as.cycle(gp)))
## gp:  (1,2,3)(4,5,6)

We have:

c(gp^3 == as.cycle(), 
  ga^2 == as.cycle(),
  gp^ga == gp^2)
## [1] TRUE TRUE TRUE

So it is an action of S3

Beat 1 2 3 4 5 6
e 1 2 3 4 5 6
a 4 6 5 1 3 2
p 2 3 1 5 6 4
p2 3 1 2 6 4 5
ap 5 4 6 2 1 3
ap2 6 5 4 3 2 1

Assuming each slot can be either 0 or 1 then we have 2^6 = 64 different records.

We can classify the beats by the number of records they contain.

|O|.|Stab| = 6 So the size of the beats is either 1, 2, 3 or 6.

  • Classification of the beats of size 1

Let B be a bit of size 1 and f the only recording inside that beat. Then we have \[p.f = f \implies p.f(1) = f(1) \implies f(2) = f(1)\] Duplicating this with p2, a, ap, ap2 yields respectively f(3) = f(1), f(4) = f(1), f(5) = f(1), f(6) = f(1).

In the end we have shown that f is constant which means f = 0 or f = 1. Both solution works so we have shown that there are exactly 2 beats of size 1.

0 0 0 0 0 0 and 1 1 1 1 1 1

  • Classification of the beats of size 2

Let B be a bit of size 2. We can write B = {f, g}. We have |Stab(f)| = 3 so Stab(f) = {e, p, p2}. And similarly for g.

\(pf = f \textrm{ and } p^2f = f \implies \\f(1) = f(2) = f(3) \textrm{ and } f(4) = f(5) = f(6)\)

So f is of the form (x,x,x,y,y,y). Furthermore we must have \(x \neq y\) because otherwise B would have size 1. So finally f is one of:

0 0 0 1 1 1 1 1 1 0 0 0

Both of those have size 2. So there are exactly 2 beats of size 2

  • Classification of the beats of size 3

Let B be a bit of size 2.

  1. First we will show that we can find a record in B of the form (x, y, z, x, z, y) where x, y, z are not all equal

f a record in B. We have |Stab(f)| = 2 so Stab(f) = {e, a} or {e, ap} or {e, ap2}.

Let’s assume Stab(f) = {e, a}. Then a.f = f. If we have also p.f = f Then B has size 1 which is absurd. So we have \(p.f \neq f\) and \(\phi(p)\) has order 3 which means B = {f, pf, p2.f}

a.f = f implies (f(4), f(6), f(5), f(1), f(3), f(2)) = (f(1), f(2), f(3), f(4), f(5), f(6))

So: f(4) = f(1), f(5) = f(3), f(6) = f(2)

Furthermore we can’t have f(1) = f(2) = f(3) otherwise f would be constant and the beat would have size 1.

So the analysis says that f is of the form (x, y, z, x, z, y) where x, y, z are not all equal.

For example (1, 0, 0, 1, 0, 0) or (0, 1, 0, 0, 0, 0, 1) or (1, 1, 0, 1, 0, 1)

  1. Here we will show that a function of the above indeed spans a beat of size 2

Let’s assume that f is of this form. Then clearly \(p.f \neq f\) and \(a.f = f\) so Stab(f) = {e, a}. So the beat of f has size 3.

  1. Here we will show that 2 different function of the above form cannot share the same beat

Let g be another function of this form (x’, y’, z’, x’, z’, y’) and suppose g is in O(f). Then g = pf or g = pf2. Let’s assume g = pf. Then g = (z, x, y, y, x, z)

So we can deduce z = y: f = (x, y, y, x, y, y) and g = (y, x, y, y, x, y) Furthermore we still have a.g = g so in particular g(5) = g(3) which means x = y. So in the end x = y = z which is absurd. So that means g is not in O(f).

  1. Conclusion

Total number of beats is the total number of triplets (x, y, z) minus the 2 constant triplets \(2*2*2 - 2 = 6\). So there are 6 beats of size 2. They are:

1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 1 1 1 0 1 1 0 1 0 1

  • Conclusion
Beat size Number
1 2
2 2
3 6
6 ?

Other actions

  • The action of S3 on S3/<p> is not faithfull. S3/<p> = {{e, p, p2}, {a, b, c}} Any element of <p> is sent to the identity. Any other element is sent to ({e, p, p2} {a, b, c})

  • There is also an action of S3 on {a, b, c}.

  • And an action of S3 on <p>

All the transitive, faithfull actions of S3

Let \(\phi\) be a transitive, faithfull set action \(S3 \rightarrow S(\mathcal{A})\). Where \(\mathcal{A}\) is any set. We note: \(g \bullet x = \phi(g)(x)\) for \(g \in S3, a \in \mathcal{A}\)

First we would like to show that \(\mathcal{A}\) has 6 elements.

Let \(a_0 \in \mathcal{A}\), we let \(f_{a_0}: S3 \rightarrow \mathcal{A}\) defined by \(f_{a_0}(g) = g \bullet a_0\)

Since the action is transitive \(f_{a_0}\) is surjective. Let’s \(g_1, g_2 \in \mathrm{S3}\). \[f_{a_0}(g_1) = f_{a_0}(g_2) \iff g_1 \bullet a_0 = g_2 \bullet a_0 \iff g_1 g_2^{-1} \bullet a_0 = a_0\]

How to see if 2 actions are isomorphic?

In all this file G is a finite group and S is a set.

An action is a group morphism \(\phi_1: G \rightarrow Aut(S)\) where S is some set. Let \(\phi_2: G \rightarrow Aut(S2)\) be another group action. 2 action are isomorphic iff there exist a set isomorphism \(f: S \rightarrow S2\) such that \[\forall g \in G, f(\phi_1(g)(x)) = \phi_2(g)(f(x))\]

The next property shows that if we have verified the property on f for \(g_1, g_2 \in G\), then the property holds for \(g_1g_2\). \[f(\phi_1(g_1g_2)(x)) = f(\phi_1(g_1)(\phi_1(g_2)(x))) = \phi_2(g_1)(f(\phi_1(g_2)x)) = \phi_2(g_1)(\phi_2(g_2)(fx)) = \phi_2(g_1g_2)(fx)\]

That means that we only need to verify the property on a set of generators for G.

Example

Let’s show that the action on {1, 2, 3} is isomorphic to the action on {{1, 2}, {1, 3}, {2, 3}} by taking f: 1 -> {2, 3} f: 2 -> {1, 3} f: 3 -> {1, 2}

f(p.1) = f(2) = {1, 3} p.f(1) = p.{2, 3} = {1, 3}

f(p.2) = f(3) = {1, 2} p.f(2) = p.{1, 3} = {1, 2}

f(a.1) = f(2) = {1, 3} a.f(1) = a.{2, 3} = {1, 3}

f(a.3) = f(3) = a.f(3) => f(3) = {1, 2}

f(b.2) = f(2) = b.f(2) => f(2) = {1, 3}

f(c.1) = f(1) = c.f(1) => f(1) = {2, 3}

So f is an isomorphism of actions.

Automorphism group of S3

Inner automorphisms

Conjugation by an element creates an automorphism. The conjugation by p has the following effect:

## a^p: (2,3)
## b^p: (1,2)
## c^p: (1,3)
## p^p: (1,2,3)
## p2^p: (1,3,2)

So conj(p) = (a c b)

Here is the conjugation by p2:

## a^p2: (1,3)
## b^p2: (2,3)
## c^p2: (1,2)
## p^p2: (1,2,3)
## p2^p2: (1,3,2)

So conj(p2) = (a b c)

Here is the conjugation by a:

## a^a: (1,2)
## b^a: (2,3)
## c^a: (1,3)
## p^a: (1,3,2)
## p2^a: (1,2,3)

So conj(a) = (b c) (p p2)

Here is the conjugation by b:

## a^b: (2,3)
## b^b: (1,3)
## c^b: (1,2)
## p^b: (1,3,2)
## p2^b: (1,2,3)

So conj(b) = (a c) (p p2)

Here is the conjugation by c:

## a^c: (1,3)
## b^c: (1,2)
## c^c: (2,3)
## p^c: (1,3,2)
## p2^c: (1,2,3)

So conj(c) = (a b)(p p2)

So together with the identity there are 6 inner automorphisms.

Structure of the automorphism group

We will show that Inner(S3) = S3 conj(a)^2 = e conj(p)^3 = e conj(p)^conj(a) = conj a-1 o conj p o conj a = conj a-1pa = conj p2 = conj(p)^2

Since the generators of Inner(S3) have the same relations as those of S3 we know the 2 groups are isomorphic.

Total group or isomorphism

We can show that there are no outer isomorphism. Indeed an automorphism maps elements to elements of the same order. There are thus 2 possibilities for mapping p and 3 possibilities for mapping a. Since a and p generate S3 this 2 images will define uniquely a mapping. There are at most 3*2 automorphisms and according to the previous paragraphs we already have 6 inner automorphisms. So all the automorphism are inner.

Matrix representation of an automorphism

Since an automorphism is uniquely defined by its image of the generators a and p we might be able to write them as a matrix. Indeed the reason we are able to write linear operators as matrix is because they are defined by their action on a basis which is a generator set of the whole vector space.

First lets try to write elements of S3 as vectors: we note a = (1, 0) and p = (0, 1) (0, x) * (1, m) = p^x * a * p^m = a * a p^x * a p^m = (1, 2*x+m)

(g1, n1) * (g2, n2) = g1n1g2n2 = g1g2inv(g2)n1g2n2 = g1g2n1^g2n2 = (g1g2, n1^g2*n2)

inv(g1) * (g2, n2) * g1 = inv(g1) * (g2*g1, n2^g1) = (g2^g1, n2^g1) conj(g1) = g1 e e g1